#include <vector>

using namespace std;

// 使网格图至少有一条有效路径的最小代价
// 给你一个 m * n 的网格图 grid 。 grid 中每个格子都有一个数字
// 对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
// 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
// 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
// 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
// 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
// 注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域
// 一开始，你会从最左上角的格子 (0,0) 出发
// 我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走
// 最终在最右下角的格子 (m - 1, n - 1) 结束的路径
// 有效路径 不需要是最短路径
// 你可以花费1的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次
// 请你返回让网格图至少有一条有效路径的最小代价
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

// 坐标压缩
class Solution 
{
public:
    int minCost(vector<vector<int>>& grid) 
    {
        // 右，左，下，上
        int move[5][2] = {{-1, -1}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int m = grid.size(), n = grid[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof dist); // 将 dist 中的元素设置成无穷大
        
        deque<int> q;
        q.emplace_front(0);
        dist[0][0] = 0;
        while(!q.empty())
        {
            // x * n + y 是表示点常用的技巧，将点（x, y）进行压缩
            // 记 pos = x * n + y，则 x = pos / n，y = pos % n  
            int pos = q.front();
            q.pop_front();
            int x = pos / n, y = pos % n;
            if(x == m - 1 && y == n - 1) return dist[x][y];
            for(int k = 1; k <= 4; ++k)
            {
                int nx = x + move[k][0], ny = y + move[k][1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n)
                {
                    // 方向相同，权值为 0
                    // 方向不同，权值为 1
                    int w = grid[x][y] == k ? 0 : 1;
                    if(dist[nx][ny] > dist[x][y] + w)
                    {
                        dist[nx][ny] = dist[x][y] + w;
                        w == 0 ? q.emplace_front(nx * n + ny) : q.emplace_back(nx * n + ny);
                    }
                }
            }
        }
        return -1;
    }
};


// 使用 pair 来表示坐标
class Solution 
{
public:
    int minCost(vector<vector<int>>& grid) 
    {
        // 右，左，下，上
        int move[5][2] = {{-1, -1}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int m = grid.size(), n = grid[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof dist); // 将 dist 中的元素设置成无穷大
        
        deque<pair<int, int>> q;
        q.emplace_front(0, 0);
        dist[0][0] = 0;
        while(!q.empty())
        {
            auto [x, y] = q.front();
            q.pop_front();
            if(x == m - 1 && y == n - 1) return dist[x][y];
            for(int k = 1; k <= 4; ++k)
            {
                int nx = x + move[k][0], ny = y + move[k][1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n)
                {
                    // 方向相同，权值为 0
                    // 方向不同，权值为 1
                    int w = grid[x][y] == k ? 0 : 1;
                    if(dist[nx][ny] > dist[x][y] + w)
                    {
                        dist[nx][ny] = dist[x][y] + w;
                        w == 0 ? q.emplace_front(nx, ny) : q.emplace_back(nx, ny);
                    }
                }
            }
        }
        return -1;
    }
};